1. Field of the Invention (Technical Field)
The invention relates to computer graphics and more particularly to computer graphics as utilized in digital map systems in aircraft avionics, consumer mapping devices or the like.
2. Background Art
The ability to display a dynamic 2 dimensional contour line as part of a real time map display system requires the ability to generate the image from a set of grided elevation data points. The present invention provides real time generation of the contour line image without requiring either preprocessed contour line images or specific electronic hardware as the prior art requires. This would provide the necessary performance to display the digital map contour lines in real time at a lower cost and in a smaller form factor.
One prior art device is disclosed in U.S. Pat. No. 4,823,287 entitled “Digital Contour Line Generator”. This device is an aircraft digital map systems that uses specific hardware to process the terrain information and requires specific hardware components. This limits the range of platforms on which the solution can be utilized, as not all are suitable for the addition of a hardware-based solution. Additionally, the cost of adding hardware either in new design or retrofit is more expensive than a solution, which can be implemented as a software only solution. Other prior art devices pre-generate the images and load them into mass storage rather than generating them on the fly. The primary disadvantage of pre-generating by any process is that it limits the geographic area which can be displayed. Furthermore, it does not allow the dynamic modification of the contour line interval, and requires mission planning or similar devices to generate and load the contour plot images into the digital map system
In addition to the prior art apparatuses described above, the “marching squares” algorithm is a common knowledge algorithm in the field of computer graphics, which can be used to generate contour line images. The existing art marching squares algorithm generates contour lines by evaluating each set of 4 data points against a contour elvation value. As shown in FIG. 1, data from the input N×M matrix 124 is processed in sets of four data points 146. For each set of 4 data points, each point is determined to be inside or outside the contour line 138, where inside and outside is determined by comparing each scalar data point value with the contour elevation value. The combination of inside and outside points is then encoded such that the encoding selects one of the 16 possible combinations 130 that a contour line can cross a set of 4 data points 146.
Using the selected intersection pattern 130, the intersection points 126 and 128 are calculated via linear interpolation. The intersection points 126 and 128 are then used as endpoints 140 and 144 of a line segment 142 drawn on the output image 132. This process is repeated for each set of four neighboring data points, for each contour elevation to be displayed on the output image. However, the marching squares algorithm does not provide the performance required for real time, dynamically updated displays on state of the art digital map hardware platforms. In addition, the marching squares approach generates extraneous data by calculating more detailed information than is needed for a digital map contour image.
Therefore, the prior art approaches cannot meet both the performance requirements and the cost requirements. Approaches that meet performance require expensive additional hardware, whereas solutions, which do not require added hardware can not meet real time dynamic performance requirements. Existing methodologies for generating contour lines focus on interpolation of data for optimal image quality, but cannot adequately meet the needs for a fast moving digital map.
The present invention maintains state information as it processes data, which results in a reduced number of operations required to generate a contour line image. This allows it to operate faster, and without requiring additional hardware devices. Thus, the faster performance of the invention allows real time dynamic contour line generation on commodity hardware, at a lower cost than the prior art methods.